113. Path Sum II
Medium

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Accepted
425,432
Submissions
847,249
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.27 (37 votes)

Premium

Solution

Approach: Depth First Traversal | Recursion

Intuition

The intuition for this approach is pretty straightforward. The problem statement asks us to find all root to leaf paths in a given binary tree. If you simply consider the depth first traversal on a tree, all it does is traverse once branch after another. All we need to do here is to simply execute the depth first traversal and maintain two things along the way:

  1. A running sum of all the nodes traversed till that point in recursion and
  2. A list of all those nodes

If ever the sum becomes equal to the required sum, and the node where this happens is a leaf node, we can simply add the list of nodes to our final solution. We keep on doing this for every branch of the tree and we will get all the root to leaf paths in this manner that add up to a certain value. Basically, these paths are branches and hence the depth first traversal makes the most sense here. We can also use the breadth first approach for solving this problem. However, that would be super heavy on memory and is not a recommended approach for this very problem. We will look into more details towards the end.

Algorithm

  1. We'll define a function called recurseTree which will take the following parameters

    • node which represents the current node we are on during recursion
    • remainingSum which represents the remaining sum that we need to find going down the tree. We can also pass the current sum in our recursive calls. However, then we'd also need to pass the required sum as an additional variable since we'd have to compare the current sum against that value. By passing in remaining sum, we can avoid having to pass additional variable and just see if the remaining sum is 0 (or equal to the value of the current node).
    • Finally, we'll have to pass a list of nodes here which will simply contain the list of all the nodes we have seen till now on the current branch. Let's call this pathNodes.
    • The following examples assume the sum to be found is 22.
  2. At every step along the way, we will simply check if the remaining sum is equal to the value of the current node. If that is the case and the current node is a leaf node, we will add the current pathNodes to the final list of paths that we have to return as a result.

  3. The problem statement here specifically mentions root to leaf paths. A slight modification is to find all root to node paths. The solutions are almost similar except that we'd get rid of the leaf check.

    • An important thing to consider for this modification is that the problem statement doesn't mention anything about the values of the nodes. That means, we can't assume them to be positive. Had the values been positive, we could stop at the node where the sum became equal to the node's value.
    • However, if the values of the nodes can be negative, then we have to traverse all the branches, all the way up to the roots. Let's look at a modified tree for reference.
  4. We process one node at a time and every time the value of the remaining sum becomes equal to the value of the current node, we add the pathNodes to our final list. Let's go ahead and look at the implementation for this algorithm.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2) where NN are the number of nodes in a tree. In the worst case, we could have a complete binary tree and if that is the case, then there would be N/2N/2 leafs. For every leaf, we perform a potential O(N)O(N) operation of copying over the pathNodes nodes to a new list to be added to the final pathsList. Hence, the complexity in the worst case could be O(N2)O(N^2).

  • Space Complexity: O(N)O(N). The space complexity, like many other problems is debatable here. I personally choose not to consider the space occupied by the output in the space complexity. So, all the new lists that we create for the paths are actually a part of the output and hence, don't count towards the final space complexity. The only additional space that we use is the pathNodes list to keep track of nodes along a branch.

    We could include the space occupied by the new lists (and hence the output) in the space complexity and in that case the space would be O(N2)O(N^2). There's a great answer on Stack Overflow about whether to consider input and output space in the space complexity or not. I prefer not to include them.

Why Breadth First Search is bad for this problem?

We did touch briefly on this in the intuition section. BFS would solve this problem perfectly. However, note that the problem statement actually asks us to return a list of all the paths that add up to a particular sum. Breadth first search moves one level at a time. That means, we would have to maintain the pathNodes lists for all the paths till a particular level/depth at the same time.

Say we are at the level 10 in the tree and that level has e.g. 20 nodes. BFS uses a queue for processing the nodes. Along with 20 nodes in the queue, we would also need to maintain 20 different pathNodes lists since there is no backtracking here. That is too much of a space overhead.

The good thing about depth first search is that it uses recursion for processing one branch at a time and once we are done processing the nodes of a particular branch, we pop them from the pathNodes list thus saving on space. At a time, this list would only contain all the nodes in a single branch of the tree and nothing more. Had the problem statement asked us the total number of paths that add up to a particular sum (root to leaf), then breadth first search would be an equally viable approach.

Report Article Issue

Comments: 30
JulesX01's avatar
Read More

Recursion time compexity should be nlogn, the max list length is logn, and n/2 leafs

50
Show 16 replies
Reply
Share
Report
aman_agarwal2189's avatar
Read More

The complexity should be nlogn.
Every path from root to leaf would be at most logN elements. and there would be atmost n/2 such path (n/2 = number of leaves in a tree).
Am i missing something here?

17
Show 3 replies
Reply
Share
Report
james_wo's avatar
Read More

tbh the biggest challenge for me was where to place the "remove last added node" line. otherwise this seems like a very standard backtracking problem

10
Reply
Share
Report
innerpieces's avatar
Read More

The time complexity should be o(n) we are only visiting each node once

24
Reply
Share
Report
lalernehl's avatar
Read More

I'm confused with the time complexity!?!? After reading other comments I get to this conclusion. Please comment!
(Please read other comments to understand how did it get to 1, 2 and 3)

In a complete tree with all leaf being part of the result list:

  1. To get to a leaf --> logN
  2. You do this N/2 times (for every leaf) -> N/2 = N
  3. Every time you do #1, you need to add a path to the solution. Copying the path --> path is logN long

O(2 * ( 1 * 3)) ---> O(N * (LogN + LogN)) ---> O(N * LogN)

5
Show 3 replies
Reply
Share
Report
list_constellation's avatar
Read More

For the python solution in line #22, any reason why we need to instantiate the inner list to a list() before adding to the global list?

if remainingSum == node.val and not node.left and not node.right:
            pathsList.append(list(pathNodes))

4
Show 2 replies
Reply
Share
Report
mpwind's avatar
Read More

backtracking?

3
Show 3 replies
Reply
Share
Report
prithul's avatar
Read More

hey can anyone explain why is time comoplexity not O(n) here . We are visiting every node only once.

5
Show 1 reply
Reply
Share
Report
nishadkumar's avatar
Read More

Nice explanation! If this is solved iteratively, will that be a disadvantage or debatable? I know recursive solution is better with respect to readability. But what is the trade off if the call stack gets bigger than necessary? Thank you though.

2
Show 5 replies
Reply
Share
Report
veginativamsi's avatar
Read More

In a complete tree, there will be at most logn nodes in a path, and in worst case every leaf node would lead to target sum, Therefore to copy logn nodes for n/2 leaf would be (n logn)

Time complexity : O(nlogn)

1
Reply
Share
Report
Success
Details
Runtime: 4 ms, faster than 97.01% of C++ online submissions for Path Sum II.
Memory Usage: 19.9 MB, less than 79.37% of C++ online submissions for Path Sum II.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/15/2021 20:31Accepted4 ms19.9 MBcpp
05/18/2021 08:21Accepted4 ms19.6 MBcpp
08/18/2020 19:54Accepted8 ms20.1 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.